//
//  ListNodeSolution.swift
//  Swift-Learning-Demo
//
//  Created by yuan xiaodong on 2022/9/27.
//  Copyright © 2022 yuan. All rights reserved.
//

import Foundation

class ListNodeSolution {
    
    /**
     160、相交链表
     给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
     如果两个链表不存在相交节点，返回 null 。
     
     解题思路1：
     这种方法最简单，使用一个哈希表
     循环使用哈希表存储l1的所有结点地址；
     然后再次循环，判断l2是否有结点在哈希表中存在
     
     解题思路2：
     比较巧妙，使用两个指针pA,pB，不断迭代。

     当pA指向为nil，将pA指向lB的头结点；pB同理。
     如果他们有相交，循环结束，即指针地址一致；如果没相交，循环结束，指针都为ni。
     还需要注意，swift当中判断指针地址是否相等是用 ===，==是判断指向的实例是否相等。
     注意3种情况：

     l1: 1 -> nil ; l2: 1 -> nil; 相交点为1
     l1: 2 -> 7 -> 8 -> 10 -> nil; l2: 1 -> 3 -> 7 -> 8 -> 10 ->nil; 相交点为8
     无相交点。
     所以判断条件是(pA == nil)，而不是(pA.next == nil)
     */
    func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
        if headA == nil || headB == nil {
            return nil
        }
        var pA: ListNode? = headA
        var pB: ListNode? = headB

        while pA !== pB {
            pA = (pA == nil) ? headB : (pA?.next)
            pB = (pB == nil) ? headA : (pB?.next)
        }
        return pA
    }
}
